/*
1.最大堆实现
2.按 3 的次幂分桶，依次取最大的分桶求和
*/
class MaxHeap {
  constructor() {
    this.heap = []
  }

  getParentIndex(index) {
    return Math.floor((index - 1) / 2)
  }

  getLeftChildIndex(index) {
    return index * 2 + 1
  }

  getRightChildIndex(index) {
    return index * 2 + 2
  }

  swap(index1, index2) {
    ;[this.heap[index1], this.heap[index2]] = [
      this.heap[index2],
      this.heap[index1]
    ]
  }

  insert(value) {
    this.heap.push(value)
    this.heapifyUp()
  }

  heapifyUp() {
    let index = this.heap.length - 1

    while (
      index > 0 &&
      this.heap[index] > this.heap[this.getParentIndex(index)]
    ) {
      const parentIndex = this.getParentIndex(index)
      this.swap(index, parentIndex)
      index = parentIndex
    }
  }

  extractMax() {
    if (this.heap.length === 0) {
      return null
    }

    const max = this.heap[0]
    this.heap[0] = this.heap.pop()
    this.heapifyDown()
    return max
  }

  heapifyDown() {
    let index = 0

    while (this.getLeftChildIndex(index) < this.heap.length) {
      const leftChildIndex = this.getLeftChildIndex(index)
      const rightChildIndex = this.getRightChildIndex(index)
      const largerChildIndex =
        rightChildIndex < this.heap.length &&
        this.heap[rightChildIndex] > this.heap[leftChildIndex]
          ? rightChildIndex
          : leftChildIndex

      if (this.heap[index] >= this.heap[largerChildIndex]) {
        break
      }

      this.swap(index, largerChildIndex)
      index = largerChildIndex
    }
  }
  getLen() {
    return this.heap.length
  }
  print() {
    console.log(this.heap)
  }
}
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxKelements = function (nums, k) {
  let res = 0
  const maxHeap = new MaxHeap()
  nums.forEach(num => {
    maxHeap.insert(num)
  })
  for (; k > 0; k--) {
    let max = maxHeap.extractMax()
    // maxHeap.print()
    res += max
    let tmp = Math.ceil(max / 3)
    // if (tmp > 1) {
    maxHeap.insert(tmp)
    // }
  }
  res += k
  return res
}

var maxKelements2 = function (nums, k) {
  let res = 0
  let obj = {}
  let max_log = 0
  nums.forEach(num => {
    let logN = Math.ceil(Math.log(num, 3))
    if (!obj[logN]) {
      obj[logN] = []
      max_log = Math.max(max_log, logN)
    }
    obj[logN].push(num)
  })
  while (max_log >= 0) {
    let tmp_arr = obj[max_log] || []
    tmp_arr = tmp_arr && tmp_arr.sort((a, b) => b - a)
    for (let i = 0; i < tmp_arr.length; i++) {
      let tmp = tmp_arr[i]
      res += tmp
      k--
      if (k == 0) return res
      let tmp_num = Math.ceil(tmp / 3)
      if (tmp_num != 1) {
        let tmp_log = Math.ceil(Math.log(tmp_num, 3))
        obj[tmp_log] = obj[tmp_log] || []
        obj[tmp_log].push(tmp_num)
      }
    }
    max_log--
  }
  res += k
  return res
}
let nums = [
  597189039, 57948756, 143524875, 379494516, 862193035, 868775043, 395597119,
  275046118, 306907315, 257034002, 476132995, 69495282, 395493151, 354621370,
  365510017, 520479568, 219063577, 159958079, 113409455, 170145739, 687892872,
  881301934, 723211517, 276655363, 635301113, 440291651, 961908086, 821028930,
  821879600, 82879805, 850787822, 547409867, 813461937, 866639644, 512259589,
  130847041, 973334294, 114942610, 233744177, 941195642, 888940360, 983125701,
  533826303, 726965368, 516401603, 312579605, 182667172, 447853195, 275822190,
  338282009
]
// nums = [1, 10, 3, 3, 3]
let k = 62126
// k = 3
console.log(maxKelements(nums, k))
console.log(maxKelements2(nums, k))

// 使用示例
const maxHeap = new MaxHeap()
// maxHeap.insert(5)
// maxHeap.insert(10)
// maxHeap.insert(3)
// maxHeap.insert(8)

// // 输出：[10, 8, 3, 5]

// console.log(maxHeap.extractMax()) // 输出：10
// console.log(maxHeap.extractMax()) // 输出：8
